package com.datastructures.avl;

/**
 * @author MaoLin Wang
 * @date 2019/11/1221:27
 */
public class AVLTreeDemo {
    public static void main(String[] args) {
       // int[]arr={4,3,6,5,7,8};
        int[]arr={10,1,12,8,9,7,6,22,33,12,31};
        AVLTree avlTree=new AVLTree();
        for (int i=0;i<arr.length;i++){
            avlTree.add(new Node(arr[i]));
        }

        System.out.println("AVL树的高度为："+avlTree.height());
        System.out.println("AVL树的左子树高度为："+avlTree.getRoot().leftHeight());
        System.out.println("AVL树的右子树高度为："+avlTree.getRoot().rightHeight());

    }
}

class AVLTree{
    private Node root;

    public void add(Node node) {
        if (root == null) {
            root = node;
        } else {
            root.add(node);
        }

    }

    public Node getRoot() {
        return root;
    }

    public void setRoot(Node root) {
        this.root = root;
    }

    public int height(){
        if (root==null){
            return 0;
        }
        return root.height(root);
    }
    public void infixOrder() {
        if (root != null) {
            root.infixOrder();
        }
    }

    //查找要删除的节点
    public Node find(int data) {
        if (root == null) {
            return null;
        } else {
            return root.find(data);
        }
    }

    //查找要删除的父节点
    public Node findparentNode(int data) {
        if (root == null) {
            return null;
        } else {
            return root.findParentNode(data);
        }
    }


    //删除节点
    public void delNode(int data) {
        if (root == null) {
            return;
        } else {
            Node targetNode = find(data);
            if (targetNode == null) {
                return;
            }
            //该树只有一个根节点
            if (root.lchild == null && root.rchild == null) {
                root = null;
                return;
            }
            Node parentNode = findparentNode(data);
            //待删除的节点是叶子节点
            if (targetNode.lchild == null && targetNode.rchild == null) {
                if (parentNode.lchild != null && parentNode.lchild.data == data) {
                    //待删除节点是父节点的左子节点
                    parentNode.lchild = null;
                } else if (parentNode.rchild != null && parentNode.rchild.data == data) {
                    //待删除节点是父节点的左子节点
                    parentNode.rchild = null;
                }
            } else if (targetNode.lchild != null && targetNode.rchild != null) {//有两颗子树
                /*
                  1.先找到要删除的节点targetNode
                 2.找到该节点的父节点parentNode
                 3.从targetNode找到最小的节点，用一个临时变量temp存储
                 4.删除该最小节点
                 5.targetNode.data=temp
                 */
                Node temp=targetNode.rchild;
                while (temp.lchild!=null){
                    temp=temp.lchild;
                }
                delNode(temp.data);
                targetNode.data=temp.data;

            } else {//待删除节点只有一颗子树
                //待删除节点有左子节点
                if (targetNode.lchild != null) {
                    if (parentNode==null){
                        root=targetNode.lchild;
                    }else {
                        //如果待删除节点是父节点的左子节点
                        if (parentNode.lchild.data == data) {
                            parentNode.lchild = targetNode.lchild;
                        } else {
                            //待删除节点是父节点的右子节点
                            parentNode.rchild = targetNode.lchild;
                        }
                    }

                } else {//待删除节点有右子节点

                    if (parentNode==null){
                        root=targetNode.rchild;
                    }else {
                        if (parentNode.lchild.data == data) {
                            //待删除节点是父节点的左子节点
                            parentNode.lchild = targetNode.rchild;
                        } else {
                            //待删除节点是父节点的右子节点
                            parentNode.rchild = targetNode.rchild;
                        }
                    }

                }
            }
        }
    }
}

class Node {
    int data;
    Node lchild;
    Node rchild;

    @Override
    public String toString() {
        return "Node{" +
                "data=" + data +
                '}';
    }

    public Node() {
    }

    public Node(int data) {
        this.data = data;
    }

    /**
     * 左旋转
     */
    private void leftRotate(){
        //1.以当前根节点的值创建新节点
        Node newNode = new Node(data);
        //2.把新的节点的左子树设置成当前节点的左子树
        newNode.lchild=lchild;
        //3.把新的节点的右子树设置成当前节点的右子树的左子树
        newNode.rchild=rchild.lchild;
        //4.把当前节点的值替换为右子树的值
        data=rchild.data;
        //5.把当前节点的右子节点设置为当前节点的右子节点的的右子节点
        rchild=rchild.rchild;
        //6.把当前节点的左子树设置为新的节点
        lchild=newNode;
    }
    /**
     * 右旋转
     */
    private void rightRotate(){
        //1.以当前根节点的值创建新节点
        Node newNode = new Node(data);
        //2.把新的节点的右子树设置成当前节点的右子树
        newNode.rchild=rchild;
        //3.把新的节点的左子树设置成当前节点的左子树的右子树
        newNode.lchild=lchild.rchild;
        //4.把当前节点的值替换为左子树的值
        data=lchild.data;
        //5.把当前节点的左子节点设置为当前节点的左子节点的的左子节点
        lchild=lchild.lchild;
        //6.把当前节点的右子树设置为新的节点
        rchild=newNode;
    }
    //返回左子树高度
    public int leftHeight(){
        if (lchild==null){
            return 0;
        }
        return height(lchild);
    }
    //返回右子树高度
    public int rightHeight(){
        if (rchild==null){
            return 0;
        }
        return height(rchild);
    }
    //返回以该节点为根节点的树的高度
    public int height(Node root){
        if (root==null){
            return 0;
        }

        int leftheight=height(root.lchild);
        int rightheight=height(root.rchild);
        return Math.max(leftheight, rightheight)+1;

    }
    //添加节点
    public void add(Node node) {
        if (node == null) {
            return;
        }
        if (node.data < this.data) {
            //当前左孩子为空
            if (this.lchild == null) {
                //让左孩子为node
                this.lchild = node;
            } else {
                this.lchild.add(node);
            }

        } else {
            if (this.rchild == null) {
                this.rchild = node;
            } else {
                this.rchild.add(node);
            }
        }
        //添加完一个节点后，如果右子树的高度-左子树的高度>1，进行左旋转
        if (rightHeight()-leftHeight()>1){
            //如果右子树的左子树的高度大于右子树的右子树的高度
            if (rchild!=null && rchild.leftHeight()>rchild.rightHeight()){
                //先对当前节点的右子节点进行右旋转
                rchild.rightRotate();
                leftRotate();
            }else {
                leftRotate();
            }
        }
        //添加完一个节点后，如果左子树的高度-右子树的高度>1，进行右旋转
        if (leftHeight()-rightHeight()>1){
            //如果左子树的右子树高度大于左子树的左子树高度
             if (lchild!=null && lchild.rightHeight()>rchild.leftHeight()){
                    //对当前节点的左子树进行左旋转
                 lchild.leftHeight();
                 //在对当前节点进行右旋转
                 rightRotate();
             }else {
                 //直接右旋转
                 rightRotate();
             }
        }
    }


    /**
     * 查找待删除节点
     *
     * @param data 待删除节点值
     * @return
     */
    public Node find(int data) {
        if (data == this.data) {
            return this;
        } else if (data < this.data) {
            if (this.lchild == null) {
                return null;
            }
            return this.lchild.find(data);
        } else {
            if (this.rchild == null) {
                return null;
            }
            return this.rchild.find(data);
        }
    }

    /**
     * 查找待删除节点的父节点
     *
     * @param data 待查询的节点的值
     * @return
     */
    public Node findParentNode(int data) {
        //当前节点是待删除节点的父节点
        if ((this.lchild != null && this.lchild.data == data) || (this.rchild != null && this.rchild.data == data)) {
            return this;
        } else {
            //查找的值比当前节点小，且当前节点有左子节点
            if (data < this.data && this.lchild != null) {
                //向左子树递归查询
                return this.lchild.findParentNode(data);
            } else if (data >= this.data && this.rchild != null) {
                //向右子树递归查询
                return this.rchild.findParentNode(data);
            } else {
                return null;
            }
        }
    }

    public void infixOrder() {
        if (this.lchild != null) {
            this.lchild.infixOrder();
        }
        System.out.println(this);
        if (this.rchild != null) {
            this.rchild.infixOrder();
        }
    }
}